package cn.zifangsky.graph;

import cn.zifangsky.disjoint.DisjSets;
import cn.zifangsky.hashtable.Map;
import cn.zifangsky.hashtable.SeparateChainHashTable;
import cn.zifangsky.queue.LinkQueue;
import cn.zifangsky.queue.PriorityQueue;
import cn.zifangsky.queue.Queue;

import java.text.MessageFormat;
import java.util.ArrayList;
import java.util.List;

/**
 * 最小生成（支撑）树
 *
 * @author zifangsky
 * @date 2019/1/28
 * @since 1.0.0
 */
public class MinSupportTree {
    private GraphList graphList;

    public MinSupportTree(GraphList graphList) {
        this.graphList = graphList;
    }

    /**
     * 使用 Prim算法 求有权图中的最小生成树
     * <p>实现思路：</p>
     * <ul>1. 使用宽度优先搜索从起点开始逐个遍历所有已经被访问顶点的邻近顶点</ul>
     * <ul>2. 如果某个邻接顶点没有被访问过，则将其权重插入到优先队列，并将其边插入到Map（为了方便后面通过权重获取对应的边信息）</ul>
     * <ul>3. 从优先队列中取出所有邻近顶点的权重最小值，将该边选为最小生成树上的边，并将相邻的那个顶点插入到最后的结果集中</ul>
     * <ul>4. 反复执行上面三步，直到最后结果集的边个数等于（图中所有顶点个数 - 1）为止</ul>
     * <p>时间复杂度：O(Elog|V|)</p>
     * @author zifangsky
     * @date 2019/1/28 17:10
     * @since 1.0.0
     */
    public void prim(){
        //图中的顶点数
        int vertexNum = graphList.getVertexNum();
        //所有顶点
        List<String> vertexList = graphList.getVertexList();
        //所有顶点信息
        GraphList.VertexNode[] list = graphList.getList();
        //定义一个List，存放已经被访问的顶点的索引
        List<Integer> visitedVertexList = new ArrayList<>(vertexNum);
        //定义一个优先队列，用于存放邻接顶点的权重
        Queue<Integer> weightQueue = new PriorityQueue<>(PriorityQueue.Mode.MIN);
        //定义一个Map，用于根据边的权重获取相应的边
        Map<Integer, Edge> edgeMap = new SeparateChainHashTable<>();
        //最后的结果集，包含最小生成树的所有边
        Queue<Edge> result = new LinkQueue<>();

        //1. 初始化
        visitedVertexList.add(0);

        //2. 如果最后结果集的边个数小于图中所有顶点个数 - 1，则一直遍历
        while (result.size() < (vertexNum - 1)){
            //2.1 遍历所有已经被访问顶点的邻近顶点
            for(Integer vertexIndex : visitedVertexList){
                //当前遍历的顶点
                GraphList.VertexNode current = list[vertexIndex];

                //2.1.1 使用宽度优先搜索遍历当前顶点的相邻顶点
                GraphList.EdgeNode temp = current.getEdgeNode();
                while (temp != null){
                    //相邻顶点的索引
                    int index = vertexList.indexOf(temp.getEndVertex());

                    //2.1.2 如果该顶点还没被访问，则做以下操作
                    if(!visitedVertexList.contains(index)){
                        //将其权重插入到优先队列
                        weightQueue.push(temp.getWeight());
                        //将其边插入到Map
                        if(!edgeMap.containsKey(temp.getWeight())){
                            edgeMap.put(temp.getWeight(), new Edge(temp.getStartVertex(), temp.getEndVertex(), temp.getWeight()));
                        }
                    }

                    temp = temp.next;
                }
            }

            if(!weightQueue.isEmpty()){
                //2.2 从优先队列中取出所有邻近顶点的权重最小值，将该边选为最小生成树上的边，并将相邻的那个顶点插入到最后的结果集中
                int minWeight = weightQueue.pop();
                Edge newEdge = edgeMap.get(minWeight);

                visitedVertexList.add(vertexList.indexOf(newEdge.getEndVertex()));
                result.push(newEdge);

                //2.3 清空优先队列和Map
                weightQueue.clear();
                edgeMap.clear();
            }
        }

        //3. 输出最小生成树的所有边
        while (!result.isEmpty()){
            Edge temp = result.pop();
            System.out.println(MessageFormat.format("start:{0}, end:{1}, weight:{2}",
                    temp.getStartVertex(), temp.getEndVertex(), temp.getWeight()));
        }
    }

    /**
     * 使用 Kruskal算法 求有权图中的最小生成树
     * <p>实现思路：</p>
     * <ul>1. 遍历图中所有边，然后将其权重存到优先队列中</ul>
     * <ul>2. 优先队列中的权重不断出队，将权重比较低的边逐渐选为最小生成树的边，要求是选取的某条边的两个顶点没有同时在最后的结果集（包含最小生成树的所有边）中</ul>
     * <p>时间复杂度：O(Elog|V|)</p>
     * @author zifangsky
     * @date 2019/1/29 10:31
     * @since 1.0.0
     */
    public void kruskal(){
        //图中的顶点数
        int vertexNum = graphList.getVertexNum();
        //所有顶点
        List<String> vertexList = graphList.getVertexList();
        //所有顶点信息
        GraphList.VertexNode[] list = graphList.getList();
        //定义一个优先队列，用于存放邻接顶点的权重
        Queue<Integer> weightQueue = new PriorityQueue<>(PriorityQueue.Mode.MIN);
        //定义一个Map，用于根据边的权重获取相应的边
        Map<Integer, List<Edge>> edgeMap = new SeparateChainHashTable<>();
        //定义一个不相交集，用于后面判断任意两个顶点是否连通
        DisjSets disjSets = new DisjSets(15);
        //最后的结果集，包含最小生成树的所有边
        Queue<Edge> result = new LinkQueue<>();

        //1. 遍历所有边，然后将其权重存到优先队列中
        for(GraphList.VertexNode current : list){
            GraphList.EdgeNode temp = current.getEdgeNode();
            while (temp != null){
                //1.1 将其边插入到Map
                Edge newEdge = new Edge(temp.getStartVertex(), temp.getEndVertex(), temp.getWeight());

                if(!edgeMap.containsKey(temp.getWeight())){
                    //如果Map中不存在指定权重的键值对，则新建一个List并插入进去
                    List<Edge> weightEdgeList = new ArrayList<>();
                    weightEdgeList.add(newEdge);
                    edgeMap.put(temp.getWeight(), weightEdgeList);

                    //1.2 将其权重插入到优先队列
                    weightQueue.push(temp.getWeight());
                }else{
                    //否则只将新边添加进去
                    List<Edge> weightEdgeList = edgeMap.get(newEdge.getWeight());
                    if(!this.checkEdgeExist(weightEdgeList, newEdge)){
                        weightEdgeList.add(newEdge);
                        edgeMap.put(newEdge.getWeight(), weightEdgeList);

                        //1.2 将其权重插入到优先队列
                        weightQueue.push(temp.getWeight());
                    }
                }

                temp = temp.next;
            }
        }

        //2. 优先队列中的权重不断出队，将权重比较低的边逐渐选为最小生成树的边
        while (result.size() < (vertexNum - 1)){
            //2.1 出队
            int minWeight = weightQueue.pop();
            //同一权重的所有边
            List<Edge> weightEdgeList = edgeMap.get(minWeight);

            //2.2 取第一条边
            Edge temp = weightEdgeList.get(0);

            //起始顶点和结束顶点的索引
            int startIndex = vertexList.indexOf(temp.getStartVertex());
            int endIndex = vertexList.indexOf(temp.getEndVertex());

            //2.3 如果两个顶点没有连通（即：没有在最后的结果集中）
            if(!disjSets.isConnected(startIndex, endIndex)){
                disjSets.union(startIndex, endIndex);
                result.push(temp);
            }

            //2.4 从List中删除已经被访问的边，并更新Map
            weightEdgeList.remove(temp);
            edgeMap.put(minWeight, weightEdgeList);
        }

        //3. 输出最小生成树的所有边
        while (!result.isEmpty()){
            Edge temp = result.pop();
            System.out.println(MessageFormat.format("start:{0}, end:{1}, weight:{2}",
                    temp.getStartVertex(), temp.getEndVertex(), temp.getWeight()));
        }
    }

    /**
     * 判断某个List中是否已经存在某条边
     */
    private boolean checkEdgeExist(List<Edge> weightEdgeList, Edge newEdge){
        for(Edge temp : weightEdgeList){
            //判断是否是同一条边
            if((temp.getStartVertex().equals(newEdge.getStartVertex()) && temp.getEndVertex().equals(newEdge.getEndVertex()))
                    || (temp.getStartVertex().equals(newEdge.getEndVertex()) && temp.getEndVertex().equals(newEdge.getStartVertex()))){
                return true;
            }
        }
        return false;
    }

}
